#include <cstdlib> 
#include <cctype> 
#include <cstring> 
#include <cstdio> 
#include <cmath> 
#include <algorithm> 
#include <vector> 
#include <string> 
#include <iostream> 
#include <sstream> 
#include <map> 
#include <set> 
#include <queue> 
#include <stack> 
#include <fstream> 
#include <iomanip> 
#include <bitset> 
#include <list> 
#include <strstream> 
using namespace std; 
#define REP(i,n) for(i=0;i<(n);++i) 
#define FOR(i,l,h) for(i=(l);i<=(h);++i) 
#define FORD(i,h,l) for(i=(h);i>=(l);--i) 
typedef vector<int> VI; 
typedef vector<double> VD; 
//typedef long long LL; 
#define MAXN 150010
int d[11][MAXN];
//int d[MAXN];
class YetAnotherORProblem2 
{ 
        public: 
        int countSequences(int N, int R) 
        { 
			int i, j, k, res = 0, count = 0;
			vector< vector<int> > graph;
			memset(d, 0, sizeof(d));
			graph.resize( N * R + 10);
			for(i = 0; i <= N * R ; i ++)
				graph[i].clear();
			for(i = 0; i < 2 * R ; i ++)
			{
				for(j = 0; j <= R && i + j <= 2 * R; j ++)
				{
					if(i + j == (i | j))
					{
						graph[i].push_back(j);
						count ++;
					//	d[i] ++;
					}	
				}
			}
		//	cout<<count<<endl;
			d[0][0] = 1;
			for(i = 1; i <= N; i ++)
			{
				for(j = 0; j < 2 * R; j ++)
				{
					for(k = 0; k < graph[j].size(); k++)
					{
						d[i][j + graph[j][k]] = (d[i][j + graph[j][k]] + d[i-1][j]) % 1000000009;
					}
				}
			}
			for(j = 0; j <= N*R;  j ++)
			{
				res = (res + d[N][j]) % 1000000009;
			}
			return res;
        } 
        
 
}; 


// Powered by FileEdit
// Powered by TZTester 1.01 [25-Feb-2003]
// Powered by CodeProcessor